/*
 * @lc app=leetcode.cn id=89 lang=cpp
 *
 * [89] 格雷编码
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<int> grayCode(int n) {
        if(0 == n) return {0};
        if(1 == n) return {0,1};
        vector<int> res = {0};
        for(int i = 0; i < n; i++)
        {
            int val = 1 << i;
            for(int j = res.size() - 1; j >= 0; --j)
            {
                res.push_back(res[j] | val);
            }
        }
        return res;
    }
};
// @lc code=end

